স্ট্রিং ম্যাচিং অ্যালগরিদম: Naive String Matching, KMP Algorithm

স্ট্রিং ম্যাচিং অ্যালগরিদমগুলি টেক্সটের মধ্যে একটি নির্দিষ্ট প্যাটার্ন খুঁজে বের করার জন্য ব্যবহৃত হয়। দুটি জনপ্রিয় স্ট্রিং ম্যাচিং অ্যালগরিদম হলো Naive String Matching Algorithm এবং KMP (Knuth-Morris-Pratt) Algorithm। এগুলি তাদের কার্যপদ্ধতি এবং কার্যক্ষমতার জন্য বিশেষভাবে পরিচিত।

১. Naive String Matching Algorithm

Naive String Matching Algorithm হল একটি সরল এবং সহজ স্ট্রিং ম্যাচিং পদ্ধতি। এই পদ্ধতিতে প্যাটার্নটি টেক্সটের প্রতিটি সম্ভাব্য অবস্থানে পরীক্ষা করা হয়।

কাজের প্রক্রিয়া:

1. টেক্সটের প্রতিটি অবস্থান থেকে প্যাটার্নের প্রথম অক্ষর শুরু করে পরীক্ষা করা হয়।
2. যদি প্রথম অক্ষরটি মেলে, তবে পরবর্তী অক্ষরগুলোর জন্য পরীক্ষা চালানো হয়।
3. যদি পুরো প্যাটার্নটি মিলে যায়, তবে প্যাটার্নের সূচক (অবস্থান) রিটার্ন করা হয়।
4. এই প্রক্রিয়াটি টেক্সটের শেষ পর্যন্ত চলতে থাকে।

টাইম কমপ্লেক্সিটি:

• Worst Case: O(n * m), যেখানে nn হল টেক্সটের দৈর্ঘ্য এবং mm হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ কোড:

def naive_string_matching(text, pattern):
    n = len(text)
    m = len(pattern)

    for i in range(n - m + 1):  # Move the pattern across the text
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:  # Found the pattern
            print(f"Pattern found at index {i}")

# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
naive_string_matching(text, pattern)

২. KMP Algorithm

KMP Algorithm একটি উন্নত স্ট্রিং ম্যাচিং অ্যালগরিদম যা প্যাটার্নের আংশিক মেলানো তথ্য ব্যবহার করে যাতে পুনরায় ম্যাচিং করার প্রয়োজনীয়তা কমে যায়। এটি প্রতি অক্ষর পুনরায় পরীক্ষা না করেই টেক্সট এবং প্যাটার্নের মধ্যে মেলানো খুঁজে বের করতে সক্ষম।

কাজের প্রক্রিয়া:

1. প্রিপ্রসেসিং (Preprocessing): একটি লংজিটুডিনাল অ্যারে (LPS Array) তৈরি করা হয়, যা প্যাটার্নের প্রতিটি অক্ষরের জন্য আংশিক মেলানো তথ্য সংরক্ষণ করে। এই LPS অ্যারে প্যাটার্নের এক অংশের অক্ষরগুলোর মধ্যে সঙ্গতিপূর্ণ উপসেট নির্দেশ করে।
2. ম্যাচিং (Matching): টেক্সটের অক্ষরগুলোর সাথে প্যাটার্নের অক্ষর তুলনা করা হয়। যদি অক্ষর মেলে, তাহলে উভয় সূচক বাড়ানো হয়। যদি না মেলে, তাহলে LPS অ্যারেকে ব্যবহার করে প্যাটার্নের সূচকটি আপডেট করা হয়।

টাইম কমপ্লেক্সিটি:

• O(n + m), যেখানে nn হল টেক্সটের দৈর্ঘ্য এবং mm হল প্যাটার্নের দৈর্ঘ্য।

উদাহরণ কোড:

def KMPSearch(text, pattern):
    m = len(pattern)
    n = len(text)

    # Create LPS array
    lps = [0] * m
    j = 0  # Length of previous longest prefix suffix
    computeLPSArray(pattern, m, lps)

    i = 0  # Index for text
    while n - i >= m:  # Only check for matches if enough characters remain
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:  # Found the pattern
            print(f"Pattern found at index {i - j}")
            j = lps[j - 1]  # Use LPS to find next position
        elif i < n and pattern[j] != text[i]:  # Mismatch after j matches
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

def computeLPSArray(pattern, m, lps):
    length = 0  # Length of the previous longest prefix suffix
    lps[0] = 0  # lps[0] is always 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

# Example usage
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
KMPSearch(text, pattern)

Naive vs KMP Algorithm

সারসংক্ষেপ

Naive String Matching Algorithm সরল কিন্তু অকার্যকর, যখন KMP Algorithm উন্নত এবং কার্যকর। KMP পদ্ধতি আংশিক মেলানো তথ্য ব্যবহার করে সময় সাশ্রয় করে এবং পুনরায় পরীক্ষা করা প্রয়োজনীয়তা কমিয়ে আনে। বিভিন্ন স্ট্রিং ম্যাচিং সমস্যায় KMP Algorithm আরও কার্যকরী।